﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortAlgos
{
    public class Sorter
    {
        static long[] _inArray = new long[20];
        public int IterationCount { get; set; }

        static Random _rand = new Random();

		/* http://en.wikipedia.org/wiki/Sorting_algorithm */

		public Sorter()
		{
			Init();
		}

        private void DoQuickSort(Sorter sorter)
        {
            sorter.Init();
            sorter.QuickSort(_inArray);
            var g = 3 * _inArray[0];
        }

		public static long[] GetRandomLongArray(int size, int arrayUpperBoundary)
		{
            long[] outArray = new long[size];

			for (int i = 0; i < size; i++)
			{
                outArray[i] = _rand.Next(0, arrayUpperBoundary);
			}

            return outArray;
		}


        public static int[] GetRandomIntArray(int size, int arrayUpperBoundary)
        {
            int[] outArray = new int[size];

            for (int i = 0; i < size; i++)
            {
                outArray[i] = _rand.Next(0, arrayUpperBoundary);
            }

            return outArray;
        }


        private void Init()
        {
            for (int i = 0; i < _inArray.Length; i++)
            {
                _inArray[i] = _rand.Next(0, 100);
            }
        } 


        #region Bubble Sort
        
        public long[] BubbleSort(long[] inputArray)
        {
			IterationCount = 0;

            for (int iterator = 0; iterator < inputArray.Length; iterator++)
            {
                for (int index = 0; index < inputArray.Length - 1; index++)
                {
                    IterationCount++;
                    if (inputArray[index] > inputArray[index + 1])
                    {
                        Swap(ref inputArray[index], ref inputArray[index + 1]);
                    }
                }
            }

			return inputArray;
        } 

        #endregion
        

        #region Quick Sort

        public long[] QuickSort(long[] inputArray)
        {
            IterationCount = 0;
            int left = 0;
            int right = inputArray.Length - 1;
            InternalQuickSort(inputArray, left, right);

			return inputArray;
        }


        private void InternalQuickSort(long[] inputArray, int left, int right)
        {
            int pivotNewIndex = Partition(inputArray, left, right);
            long pivot = inputArray[(left + right) / 2];
            if (left < pivotNewIndex-1)
                InternalQuickSort(inputArray, left, pivotNewIndex - 1);
            if (pivotNewIndex < right)
                InternalQuickSort(inputArray, pivotNewIndex, right);
        }

        //This operation returns a new pivot everytime it is called recursively
        //and swaps the array elements based on pivot value comparison
        private int Partition(long[] inputArray, int left, int right)
        {
            int i = left, j = right;
            long pivot = inputArray[(left + right) / 2];

            while (i <= j)
            {
                while (inputArray[i] < pivot)
                {
                    i++;
                }
                while (inputArray[j] > pivot)
                {
                    j--;
                }
                if (i <= j)
                {
                    SwapWithTemp(ref inputArray[i], ref inputArray[j]);
                    i++; j--;
                }
            }
            return i;
        }

        #endregion
        

        #region Helper Methods
        
        private void Swap(ref long valOne, ref long valTwo)
        {
            valOne = valOne + valTwo;
            valTwo = valOne - valTwo;
            valOne = valOne - valTwo;
        }

        private void SwapWithTemp(ref long valOne, ref long valTwo)
        {
            long temp = valOne;
            valOne = valTwo;
            valTwo = temp;
        } 

        #endregion

    }
}
